package q102_levelOrder;

import CommonClass.Common.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution_1 {
    public static void main(String[] args) {

    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }
        // LinkedList以队列的形式创建
        // 一般来说Queue被定义为单端队列来使用
        // 而Deque则是被定义为双端队列来使用
        // 队列的特点 —— 先进先出！
        // 所以在层内的顺序是先进左节点 然后右节点
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        // offer方法是将指定的元素添加到LinkedList的最后一个元素
        // 作为List使用时,一般采用add / get方法来 压入/获取对象。
        // 作为Queue使用时,才会采用 offer/poll/take等方法作为链表对象时,offer等方法相对来说没有什么意义，这些方法是用于支持队列应用的。
        queue.offer(root);
        // 开始循环 当目前的队列不为空的时候
        while (!queue.isEmpty()) {
            // 用来存储答案
            List<Integer> level = new ArrayList<Integer>();
            // 存储当前队列的长度，也就是这一层
            int currentLevelSize = queue.size();
            // 对这一层的每一个节点进行遍历
            for (int i = 1; i <= currentLevelSize; ++i) {
                // 首先是将这个节点poll出来并加入到level中
                TreeNode node = queue.poll();
                level.add(node.val);
                // 关键在于，poll出来的节点则可能会生成两个子节点，所以要将其加入到 队尾
                // 这里要注意的是，currentLevelSize只是当前这一层， 比如一个1节点有2 3两个子节点
                // 那么将1 poll 出来后，queue正好又加入了两个子节点，结束循环后，currentLevelSize恰好是下一层的节点数量
                // 于是就可以进行新一轮的循环，直到queue为空
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // 将level加入答案
            ret.add(level);
        }
        return ret;
    }
}
